import java.util.Comparator;
import java.util.PriorityQueue;

class Student {

}

class IntComp implements Comparator<Integer> {
    //这是把其变成大根堆
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
class Solution {
    //Top-k 问题：
    //前k个最小的，我们建前 k 个元素的大根堆
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        //默认为小堆，我们传比较器
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,new IntComp());

        //把前k个元素放入到堆中
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        //之后从第 N-k 个数据开始比较知道比较结束
        //这里是求前k个最小的，所以把第 N-k 个数据和 堆顶进行比较，如果 N-k 小的话就是 删堆顶，入第N-k的元素堆
        for (int i = k; i < arr.length; i++) {
            int peekval = priorityQueue.peek();
            if (arr[i] < peekval) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        //把堆里的元素放到数组中
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }

    //直接把数组建堆，返回前k个元素
    public int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}
public class Test {

    public static void main3(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(10);
        priorityQueue.offer(20);
        priorityQueue.offer(8);
        priorityQueue.offer(4);
        priorityQueue.offer(56);

        if (priorityQueue.isEmpty()) {
            System.out.println("为空");
        }else {
            System.out.println("不为空");
        }

//        System.out.println("有效数组个数 " + priorityQueue.size());

//        System.out.println("优先级队列的堆顶：" + priorityQueue.peek());
//
//        System.out.println("出优先级最高的数据：" + priorityQueue.poll());
//
//        System.out.println("删除之后的优先级队列的堆顶：" + priorityQueue.peek());
    }
    public static void main2(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(10);
        priorityQueue.offer(20);
        priorityQueue.offer(8);

        //这样我们来看看优先级队列的顶部就可以看出我们的默认堆
        System.out.println(priorityQueue.peek());

        System.out.println("=============");
        //变成大根堆，我们传一个比较器
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(new IntComp());
        priorityQueue1.offer(10);
        priorityQueue1.offer(20);
        priorityQueue1.offer(8);
        //这样我们得到的就是大根堆
        System.out.println(priorityQueue1.peek());

    }
    public static void main1(String[] args) {

        //不能存放null
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(null);

        //PriorityQueue不能放入不能比较的对象
        PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();

        priorityQueue2.offer(new Student());

    }
}
